import java.util.Arrays;

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] check = new boolean[n][n];
        for(int i = n - 1; i >= 0; i--){
            for(int j = i; j < n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    if(j > i + 1) check[i][j] = check[i + 1][j - 1];
                    else check[i][j] = true;
                }
            }
        }
        int[] dp = new int[n];// 以 i 位置为结尾，0 ~ i 的子串被分割为回文串的最少次数
        // 初始化
        Arrays.fill(dp, n - 1);
        //dp[0] = 0;
        // 状态转移方程
        for(int i = 0; i < n; i++){
            if(check[0][i]) dp[i] = 0;
            else{
                for(int j = i; j > 0; j--){
                    if(check[j][i]){
                        dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp[n - 1];
    }
}